package binary

import "math"

// https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/
// 范围位运算
// 最直接解法: 直接整个范围内的所有数字做位运算
// 优化后算法: 找规律: 从区间的两个数 left 和 right 的最高1位开始算，直到最高位不同
// 比如[5, 7] 分别是101 和 111，相同最高1位 就只有第一位，因此答案就是4
// 为什么可以这么算: 最高1位 必须在同一个位置，如果不同，在这个区间内就必然出现对应位置为0 的数字
// 也可以用排除法: 位数不同的情况: 左区间更早: 不可能，违背了左区间更小的前提; 右区间更早: 那在这个区间遍历的过程中
// 左区间比当期位置更低的1位 一定会被重置成0
func RangeBitwiseAnd(m int, n int) int {
	if m > n {
		return 0
	} else if m == n {
		return m & n
	}
	// 算出左右区间各自的1位出现位置
	leftOneBitArr := getBitOneOccurPosArr(m)
	rightOneBitArr := getBitOneOccurPosArr(n)

	leftIndex := len(leftOneBitArr) - 1
	rightIndex := len(rightOneBitArr) - 1

	ret := 0
	for leftIndex >= 0 && rightIndex >= 0 {
		if leftOneBitArr[leftIndex] != rightOneBitArr[rightIndex] {
			break
		}
		ret += int(math.Pow(2, float64(leftOneBitArr[leftIndex])))
		leftIndex--
		rightIndex--
	}
	return ret
}

// 公共方法: 返回一个整数 用二进制表示之后，1位 出现的所有位置下标
// 低位 在数组之前
func getBitOneOccurPosArr(m int) []int {
	pos := 0
	retArr := make([]int, 0)
	for m != 0 {
		if 1 == m%2 {
			retArr = append(retArr, pos)
		}
		pos++
		m /= 2
	}
	return retArr
}
